use std::collections::{HashMap, VecDeque};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let dx = vec![0, 1, 0, -1];
    let dy = vec![1, 0, -1, 0];
    let mut founded = false;
    let mut visited = HashMap::new();
    let mut q = VecDeque::new();
    q.push_back(start);
    visited.insert(start, None);
    while let Some(cur) = q.pop_front() {
        if cur.0 == end.0 && cur.1 == end.1 {
            founded = true;
            break;
        }
        for i in 0..4 {
            let x = cur.0.wrapping_add_signed(dx[i]);
            let y = cur.1.wrapping_add_signed(dy[i]);
            let node = (x, y);
            if x >= maze.len()
                || y >= maze[0].len()
                || maze[x][y] == '#'
                || visited.contains_key(&node)
            {
                continue;
            }
            q.push_back(node);
            visited.insert(node, Some(cur));
        }
    }
    let mut path = vec![];
    if founded {
        path.push(end);
        let mut cur = end;
        while let Some(p) = visited[&cur] {
            path.push(p);
            cur = p;
        }
    }
    path.reverse();
    path
}
